from collections import defaultdict
from typing import List

# lc2003 树上启发式合并
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
    n = len(parents)
    mex = [0] * n
    g = defaultdict(list)
    for i in range(1,n):
        v = parents[i]
        g[v].append(i)
    def dfs(i):
        inSet = set()
        mex[i] = 1
        for nxt in g[i]:
            s = dfs(nxt)
            if len(s) > len(inSet): #删除这个会降低很多速度
                inSet,s = s,inSet
            for x in s:
                inSet.add(x)
            if mex[nxt] > mex[i]:
                mex[i] = mex[nxt]
        inSet.add(nums[i])
        while mex[i] in inSet:
            mex[i]+=1
        return inSet
    dfs(0)
    return mex